#ifndef _MC_CPP_
#define _MC_CPP_

#include"util.h"
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<ctime>
#include"patterns.h"

class McSimulator{
  public :

    int board[MAX_BOARD * MAX_BOARD];
    int next_stone[MAX_BOARD * MAX_BOARD];
    int final_status[MAX_BOARD * MAX_BOARD];
    int avaiable[MAX_BOARD*MAX_BOARD];
    int count_empty;
    int step;
    int ko_i, ko_j;
    int lastpos;
    int lastsecondpos;
    int firsttime;
    int secondtime;
    int thirdtime;
    int patterntime;
    int canmovetime;

    McSimulator() {
    }
    McSimulator(int* b, int * n) {
        memcpy(board, b, sizeof(board));
        memcpy(next_stone, n, sizeof(next_stone));
        count_empty = 0;
        for (int i= 0; i < board_size; i++) 
            for (int j = 0; j < board_size; j++) {
                if (board[POS(i,j)] == EMPTY) {
                    avaiable[count_empty++] = POS(i,j);
                }
            }
        step = 0;
        firsttime = secondtime=thirdtime = canmovetime = patterntime = 0;
    }

    void refresh(int *b, int *n) {
        memcpy(board, b, sizeof(board));
        memcpy(next_stone, n, sizeof(next_stone));
        count_empty = 0;
        step = 0;
        for (int i= 0; i < board_size; i++) 
            for (int j = 0; j < board_size; j++) {
                if (board[POS(i,j)] == EMPTY) {
                    avaiable[count_empty++] = POS(i,j);
                }
            }
    }
    void refreshtime(){
        firsttime = secondtime=thirdtime = canmovetime = patterntime = 0;
    }

    double simulate(int i, int j, int color) {

        int oricolor = color;
        play_move(i,j,color);
        lastpos = POS(i,j);
        lastsecondpos = -1;
        step = 0;
        while((lastpos >=0 || lastsecondpos >=0 || step == 0) && step < 170) {
            step++;
            color = OTHER_COLOR(color);
            int x=-1,y=-1;
            gen_random_move(x,y,color);
            play_move(x,y,color);
//            fprintf(stderr,"%d %d %d\n",x,y, step);
//            for(int k =0; k < 169; k++) {
//                fprintf(stderr, "%d ", board[k]);
//            }
//            fprintf(stderr, "\n");
            lastsecondpos = lastpos;
            lastpos = POS(x,y);
        }
//        fprintf(stderr," finish simulate \n",lastpos,lastsecondpos);
        float score = compute_final_score();

        if(oricolor == WHITE){
//            fprintf(stderr,"win %d %d\n",lastpos,lastsecondpos);
            return score;
        }
        if(oricolor == BLACK){
//            fprintf(stderr,"win %d %d\n",lastpos,lastsecondpos);
            return -score;
        }
//        fprintf(stderr,"lose %d %d\n",lastpos,lastsecondpos);
        return 0;
    }
    
    

    void gen_random_move(int & ri, int &rj, int color) {
         int x,y;

         int candidate_move[14*14],second_candidate[14*14],tot=0,stot=0;
//         clock_t time = clock();
         if (lastpos >=0) {
            x = I(lastpos);
            y = J(lastpos);
            for(int k =0; k < 8; k++){
                int nx=x+multideltai[k],ny=y+multideltaj[k];
                if ( on_board(nx,ny) && board[POS(nx,ny)]==EMPTY &&matchpattern(nx,ny, color,board) )
                    candidate_move[tot++] = POS(nx,ny);

            }
        }

        if (lastsecondpos >=0) {
            x = I(lastsecondpos);
            y = J(lastsecondpos);
            for(int k =0; k < 8; k++){
                int nx=x+multideltai[k],ny=y+multideltaj[k];
                if ( on_board(nx,ny) && board[POS(nx,ny)]==EMPTY &&matchpattern(nx,ny, color,board) )
                    candidate_move[tot++] = POS(nx,ny);
            }
        }
//        firsttime+= clock()-time;
        
//        time = clock();
        if (tot > 0) {
            int res = candidate_move[rand() % tot];
            ri = I(res);
            rj = J(res);
            return;
        }
//        fprintf( stderr,"stot: %d\n" ,stot);
        // if (stot > 0) {

        //     int res = second_candidate[random() % stot];
        //     ri = I(res);
        //     rj = J(res);
        //     return;
        // }
        while(count_empty > 0) {
            int choose = rand() % count_empty;
            int move = avaiable[choose];
            if (!canput(I(move),J(move),color)) {
                count_empty--;
                avaiable[choose] = board[count_empty];
                continue;
            }
            ri = I(move);
            rj = J(move);
            // secondtime+= clock()-time;
            // time = clock();
            return;
        }
        for (int i= 0; i < board_size; i++) 
            for (int j = 0; j < board_size; j++) {
                if (board[POS(i,j)] == EMPTY)
                    avaiable[count_empty++] = POS(i,j);
                if (canput(i,j,color)) {
                    // fprintf(stderr, "canput %d ,%d, %d\n", i,j,color);
                    candidate_move[tot++] = POS(i,j);
                }
            }
        // thirdtime+= clock()-time;
        // time = clock();
//        fprintf(stderr, "mc, gen_random_move\n");
        if (tot > 0) {
            int res = candidate_move[rand() % tot];
            ri = I(res);
            rj = J(res);
            return;
        }
        ri = -1;
        rj = -1;
    }
    
    float compute_final_score(){
        float score = komi;
        int i, j;
        compute_final_status();
        for (i = 0; i < board_size; i++)
            for (j = 0; j < board_size; j++) {
                int status = get_final_status(i, j);
                if (status == BLACK_TERRITORY)
                    score--;
                else if (status == WHITE_TERRITORY)
                    score++;
                else if ((status == ALIVE) ^ (get_board(i, j) == WHITE))
                    score--;
                else
                    score++;
            }
        return score;
    }
    
    int canput(int ai, int aj, int color) {
//        int x = clock();
        if (on_board(ai,aj) && legal_move(ai, aj, color) && !suicide(ai, aj, color)) {
            /* Further require the move not to be suicide for the opponent... */
            if (!suicide(ai, aj, OTHER_COLOR(color))) {
//                canmovetime+=clock()-x;
                return 1;
            }
            else {
                /* ...however, if the move captures at least one stone,
                 * consinder it anyway.
                 */
                for (int k = 0; k < 4; k++) {
                    int bi = ai + deltai[k];
                    int bj = aj + deltaj[k];
                    if (on_board(bi, bj) && get_board(bi, bj) == OTHER_COLOR(color)) {
//                        canmovetime+=clock()-x;
                        return 1;
                    }
                }
            }
        }
//        canmovetime+=clock()-x;
        return 0;
    }

    int legal_move(int i, int j, int color)  {
        int other = OTHER_COLOR(color);
  
        /* Pass is always legal. */
        if (pass_move(i, j))
            return 1;

        /* Already occupied. */
        if (get_board(i, j) != EMPTY)
            return 0;

        /* Illegal ko recapture. It is not illegal to fill the ko so we must
         * check the color of at least one neighbor.
         */
        if (i == ko_i && j == ko_j
            && ((on_board(i - 1, j) && get_board(i - 1, j) == other)
                || (on_board(i + 1, j) && get_board(i + 1, j) == other)))
            return 0;

        return 1;
    }

    void play_move(int i, int j, int color)
    {
        int pos = POS(i, j);
        int captured_stones = 0;
        int k;

        /* Reset the ko point. */
        ko_i = -1;
        ko_j = -1;

        /* Nothing more happens if the move was a pass. */
        if (pass_move(i, j))
            return;

        /* If the move is a suicide we only need to remove the adjacent
         * friendly stones.
         */
        if (suicide(i, j, color)) {
            for (k = 0; k < 4; k++) {
                int ai = i + deltai[k];
                int aj = j + deltaj[k];
                if (on_board(ai, aj)
                    && get_board(ai, aj) == color)
                    remove_string(ai, aj);
            }
            return;
        }

        /* Not suicide. Remove captured opponent strings. */
        for (k = 0; k < 4; k++) {
            int ai = i + deltai[k];
            int aj = j + deltaj[k];
            if (on_board(ai, aj)
                && get_board(ai, aj) == OTHER_COLOR(color)
                && !has_additional_liberty(ai, aj, i, j))
                captured_stones += remove_string(ai, aj);
        }

        /* Put down the new stone. Initially build a single stone string by
         * setting next_stone[pos] pointing to itself.
         */
        board[pos] = color;
        next_stone[pos] = pos;

        /* If we have friendly neighbor strings we need to link the strings
         * together.
         */
        for (k = 0; k < 4; k++) {
            int ai = i + deltai[k];
            int aj = j + deltaj[k];
            int pos2 = POS(ai, aj);
            /* Make sure that the stones are not already linked together. This
             * may happen if the same string neighbors the new stone in more
             * than one direction.
             */
            if (on_board(ai, aj) && board[pos2] == color && !same_string(pos, pos2)) {
                /* The strings are linked together simply by swapping the the
                 * next_stone pointers.
                 */
                int tmp = next_stone[pos2];
                next_stone[pos2] = next_stone[pos];
                next_stone[pos] = tmp;
            }
        }

        /* If we have captured exactly one stone and the new string is a
         * single stone it may have been a ko capture.
         */
        if (captured_stones == 1 && next_stone[pos] == pos) {
            int ai, aj;
            /* Check whether the new string has exactly one liberty. If so it
             * would be an illegal ko capture to play there immediately. We
             * know that there must be a liberty immediately adjacent to the
             * new stone since we captured one stone.
             */
            for (k = 0; k < 4; k++) {
                ai = i + deltai[k];
                aj = j + deltaj[k];
                if (on_board(ai, aj) && get_board(ai, aj) == EMPTY)
                    break;
            }
    
            if (!has_additional_liberty(i, j, ai, aj)) {
                ko_i = ai;
                ko_j = aj;
            }
        }
    }
    void
        set_final_status_string(int pos, int status)
    {
        int pos2 = pos;
        do {
            final_status[pos2] = status;
            pos2 = next_stone[pos2];
        } while (pos2 != pos);
    }

    void compute_final_status(void)
    {
        int i, j;
        int pos;
        int k;

        for (pos = 0; pos < board_size * board_size; pos++)
            final_status[pos] = UNKNOWN;
  
        for (i = 0; i < board_size; i++)
            for (j = 0; j < board_size; j++)
                if (get_board(i, j) == EMPTY)
                    for (k = 0; k < 4; k++) {
                        int ai = i + deltai[k];
                        int aj = j + deltaj[k];
                        if (!on_board(ai, aj))
                            continue;
                        /* When the game is finished, we know for sure that (ai, aj)
                         * contains a stone. The move generation algorithm would
                         * never leave two adjacent empty vertices. Check the number
                         * of liberties to decide its status, unless it's known
                         * already.
                         *
                         * If we should be called in a non-final position, just make
                         * sure we don't call set_final_status_string() on an empty
                         * vertex.
                         */
                        pos = POS(ai, aj);
                        if (final_status[pos] == UNKNOWN) {
                            if (get_board(ai, aj) != EMPTY) {
                                if (has_additional_liberty(ai, aj, i, j))
                                    set_final_status_string(pos, ALIVE);
                                else
                                    set_final_status_string(pos, DEAD);
                            }
                        }
                        /* Set the final status of the (i, j) vertex to either black
                         * or white territory.
                         */
                        if (final_status[POS(i, j)] == UNKNOWN) {
                            if ((final_status[pos] == ALIVE) ^ (get_board(ai, aj) == WHITE))
                                final_status[POS(i, j)] = BLACK_TERRITORY;
                            else
                                final_status[POS(i, j)] = WHITE_TERRITORY;
                        }
                    }
    }

    int
        get_final_status(int i, int j)
    {
        return final_status[POS(i, j)];
    }

    void set_final_status(int i, int j, int status)
        {
            final_status[POS(i, j)] = status;
        }

    int
    suicide(int i, int j, int color)
        {
            int k;
            for (k = 0; k < 4; k++)
                if (provides_liberty(i + deltai[k], j + deltaj[k], i, j, color))
                    return 0;

            return 1;
        }

    int
    remove_string(int i, int j)
        {
            int pos = POS(i, j);
            int removed = 0;
            do {
                board[pos] = EMPTY;
                avaiable[count_empty++] = pos;
                removed++;
                pos = next_stone[pos];
            } while (pos != POS(i, j));

            return removed;
        }

    int
    get_board(int i, int j)
        {
            return board[i * board_size + j];
        }


    int
    has_additional_liberty(int i, int j, int libi, int libj)
        {
            int pos = POS(i, j);
            do {
                int ai = I(pos);
                int aj = J(pos);
                int k;
                for (k = 0; k < 4; k++) {
                    int bi = ai + deltai[k];
                    int bj = aj + deltaj[k];
                    if (on_board(bi, bj) && get_board(bi, bj) == EMPTY
                        && (bi != libi || bj != libj))
                        return 1;
                }

                pos = next_stone[pos];
            } while (pos != POS(i, j));

            return 0;
        }
    
    int
    provides_liberty(int ai, int aj, int i, int j, int color)
        {
            /* A vertex off the board does not provide a liberty. */
            if (!on_board(ai, aj))
                return 0;

            /* An empty vertex IS a liberty. */
            if (get_board(ai, aj) == EMPTY)
                return 1;

            /* A friendly string provides a liberty to (i, j) if it currently
             * has more liberties than the one at (i, j).
             */
            if (get_board(ai, aj) == color)
                return has_additional_liberty(ai, aj, i, j);

            /* An unfriendly string provides a liberty if and only if it is
             * captured, i.e. if it currently only has the liberty at (i, j).
             */
            return !has_additional_liberty(ai, aj, i, j);
        }
    
    int
    same_string(int pos1, int pos2)
        {
            int pos = pos1;
            do {
                if (pos == pos2)
                    return 1;
                pos = next_stone[pos];
            } while (pos != pos1);
  
            return 0;
        }

};
#endif
